import java.util.Arrays;

public class Test {
    public static int majorityElement(int[] array) {
        int ret = array[0];
        int count = 0;
        for(int i = 0; i < array.length; i++) {
            if(ret == array[i]) {
                count++;
            } else {
                count--;
            }
            if(count == 0) {
                ret = array[i + 1];
            }
        }
        return ret;
    }
    public static void main4(String[] args) {
        int[] arr = {1, 1, 1, 1, 1, 2, 3, 4};
        int ret = majorityElement(arr);
        System.out.println(ret);
    }
    public static void main3(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 1, 1, 1, 1, 1};
        Arrays.sort(array);
        System.out.println(array[array.length / 2]);
    }
    public static int findOnly(int[] array) {
        int onlyOne = 0;
        for(int i = 0 ;i < array.length; i++) {
            onlyOne ^= array[i];
        }
        return onlyOne;
    }
    public static void main2(String[] args) {
        int[] array = {1, 2, 3, 2, 1};
        int ret = findOnly(array);
        System.out.println(ret);
    }
    public static int[] findSum(int[] array, int target) {
        int[] arr = new int[2];
        for(int i = 0; i < array.length; i++) {
            for(int j = i + 1; j < array.length; j++) {
                if(array[i] + array[j] == target) {
                    arr[0] = i;
                    arr[1] = j;
                    return arr;
                }
            }
        }
        return null;
    }
    public static void main1(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        int target = 9;
        int[] arr = findSum(array, target);
        System.out.println(Arrays.toString(arr));
    }
//    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 4, 345, 223, 22, 12, 6};
//        int target = 10;
//        Arrays.sort(nums);
//        int flag = 0;
//        for(int i = 0; i < nums.length; i++) {
//            if(target >= nums[i]) {
//                break;
//            }
//            flag++;
//        }
//        int aaa = 0;
//        int j;
//        for(int i = 0; i < flag; i++) {
//            for(j = i; j < flag; j++) {
//                if(nums[j] + nums[j + 1] == target) {
//                    aaa = j;
//                    break;
//                }
//            }
//            if(aaa == j) {
//                break;
//            }
//        }
//        System.out.println(aaa + " " + (aaa + 1));
//    }
}
